import java.sql.SQLOutput;
import java.util.*;

public class Main {
    /*
    前k个高频单词
     */
    public List<String> topKFrequent(String[] words, int k) {


    }
    /*
    随机链表的复制
     */
    public Node copyRandomList(Node head) {
        HashMap<Node,Node> map = new HashMap<>();

        Node cur = head;
        while (cur != null) {//新旧 节点对应存入map
            Node cont = new Node(cur.val);
            map.put(cur,cont);
            cur = cur.next;
        }
        cur = head;
        Node ret = map.get(cur);
        while (cur != null) {
            if (cur.next != null) {
                map.get(cur).next = map.get(cur.next);
            }
            if (cur.random != null) {
                map.get(cur).random = map.get(cur.random);
            }
            cur = cur.next;
        }
        return ret;
    }
    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    /*
    只出现一次的数字
    给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。
    找出那个只出现了一次的元素。

    你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
     */
    public int singleNumber(int[] nums) {
        //set 的使用
        /*
        HashSet<Integer> hashSet = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (hashSet.contains(nums[i])) {//set中是否有 key
                //删除key
                hashSet.remove(nums[i]);
            }else {
                hashSet.add(nums[i]);
            }
        }
        Object[] ret = hashSet.toArray();
        return (int)ret[0];
        */
        //更快速的算法
        int ret = 0;
        for (int i = 0; i < nums.length; i++) {
            ret ^= nums[i];
        }
        return ret;
    }
    /*
    宝石与石头
    给你一个字符串 jewels 代表石头中宝石的类型，另有一个字符串 stones 代表你拥有的石头。 stones 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。

    字母区分大小写，因此 "a" 和 "A" 是不同类型的石头
     */
    public int numJewelsInStones(String jewels, String stones) {
        int sum = 0;
        HashMap<Character,Integer> hashMap = new HashMap<>();
        for (int i = 0; i < stones.length(); i++) {
            if (hashMap.containsKey(stones.charAt(i))) {//map中是否有 key
                //让key 所对应的value 值自增1
                hashMap.put(stones.charAt(i), hashMap.get(stones.charAt(i)) + 1);
            }else {
                hashMap.put(stones.charAt(i), 1);
            }
        }
        for (int i = 0; i < jewels.length(); i++) {
            //返回key所对应的value值,没有则返回0
            sum += hashMap.getOrDefault(jewels.charAt(i), 0);
        }

        return sum;
    }
    /*
    给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot
    具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
    二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
     */
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null && subRoot == null) {
            return true;
        }
        if (root == null && subRoot != null || root != null && subRoot == null) {
            return false;
        }
        if (isSameTree(root, subRoot)) {//判断当前root的节点往下 与 subRoot是否相等
            return true;
        }
        if (isSubtree(root.left, subRoot)) {//如果当前root与subRoot不相等,则root向左走
            return true;
        }
        if (isSubtree(root.right, subRoot)) {//再不相等root向右走
            return true;
        }
        return false;
    }
    /*
    给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
    如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的
     */
    public boolean isSameTree(TreeNode p, TreeNode q) {//判断树是否相等
        if (p == null && q == null) {//情况1 都为空
            return true;
        }else if (p == null && q != null || p != null && q == null) {//情况2 一个为空一个不为空
            return false;
        }
        if (p.val != q.val) {//情况3 都不为空  《如果当前相等了,则继续往后走》
            return false;
        }
        if (!isSameTree(p.left , q.left)) {//判断左子树及其左子树中的左右子树（递归）
            return false;
        }
        if (!isSameTree(p.right , q.right)) {//判断右子树
            return false;
        }


        return true;//上列 情况2 情况3 都不满足 则返回true
    }
    /*
    给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
    把每个子树都交换
     */
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        if (root.left == null && root.right == null) {//如果左右为空,则不用交换
            return root;//不能返回null,因为如果只有一个根时,左右子树也是空
        }
        TreeNode cmp = root.left;//交换左右子树
        root.left = root.right;
        root.right = cmp;

        invertTree(root.left);//不用接收他们的返回值
        invertTree(root.right);

        return root;//在递归收尾回来的时候再进行返回(根)即可
    }
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /*
    给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
    有效字符串需满足：

    左括号必须用相同类型的右括号闭合。
    左括号必须以正确的顺序闭合。
    每个右括号都有一个对应的相同类型的左括号。
     */
    class Solution {
        public boolean isValid(String s) {
            Stack<Character> test = new Stack<>();
            for (int i = 0; i < s.length(); i++) {
                char cmp = s.charAt(i);
                if (cmp == '(' || cmp == '[' || cmp == '{') {
                    test.push(cmp);
                }else if (cmp == ')') {
                    if (test.isEmpty()) {
                        return false;
                    }
                    if (test.pop() != '(') {
                        return false;
                    }
                }else if (cmp == ']') {
                    if (test.isEmpty()) {
                        return false;
                    }
                    if (test.pop() != '[') {
                        return false;
                    }
                }else if (cmp == '}') {
                    if (test.isEmpty()) {
                        return false;
                    }
                    if (test.pop() != '{') {
                        return false;
                    }
                }
            }
            if (!test.isEmpty()) {
                return false;
            }
            return true;
        }
    }
    /*
    给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
    请你计算该表达式。返回一个表示表达式值的整数
     */
    public int evalRPN(String[] tokens) {
        Stack<Integer> test = new Stack<>();
        for (int i = 0; i < tokens.length; i++) {
            if (!tokens[i].equals("+") && !tokens[i].equals("-")
                    && !tokens[i].equals("*") && !tokens[i].equals("/")) {
                int cmp = Integer.valueOf(tokens[i]);
                test.push(cmp);
            } else {
                int right = test.pop();
                int left = test.pop();
                switch (tokens[i]) {
                    case "+":
                        test.push(left + right);
                        break;
                    case "-":
                        test.push(left - right);
                        break;
                    case "*":
                        test.push(left * right);
                        break;
                    case "/":
                        test.push(left / right);
                        break;
                }
            }
        }
        return test.pop();
    }
    /*
    设计循环队列
     */
    class MyCircularQueue {
        private int[] arr;
        private int left;//队头
        private int right;//队尾

        public MyCircularQueue(int k) {
            arr = new int[k+1];//留一个空间 防止队尾和队头在相同位置
            //队尾队头在相同位置时：数组为空
            //队尾 在 队头 左边一个位置时：数组已满
        }

        public boolean enQueue(int value) {
            if (isFull()) {
                return false;
            }
            arr[right % arr.length] = value;//防止大于数组长度， 不用担心访问错误，因为这个数组是环（循环）
            right++;
            return true;
        }

        public boolean deQueue() {//删除第一个（队列 先进先出）
            if (isEmpty()) {
                return false;
            }
            left++;
            return true;
        }

        public int Front() {//返回队首
            if (isEmpty()) {
                return -1;
            }
            return arr[left % arr.length];

        }

        public int Rear() {//返回队尾
            if (isEmpty()) {
                return -1;
            }
            return arr[(right-1) % arr.length];//队尾元素
        }

        public boolean isEmpty() {
            if (left == right) {
                return true;
            }
            return false;
        }

        public boolean isFull() {
            if ((right+1) % arr.length == left) {
                return true;
            }
            return false;
        }
    }

    /**
     * Your MyCircularQueue object will be instantiated and called as such:
     * MyCircularQueue obj = new MyCircularQueue(k);
     * boolean param_1 = obj.enQueue(value);
     * boolean param_2 = obj.deQueue();
     * int param_3 = obj.Front();
     * int param_4 = obj.Rear();
     * boolean param_5 = obj.isEmpty();
     * boolean param_6 = obj.isFull();
     */
    /*
    请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
    实现 MyQueue 类：

    void push(int x) 将元素 x 推到队列的末尾
    int pop() 从队列的开头移除并返回元素
    int peek() 返回队列开头的元素
    boolean empty() 如果队列为空，返回 true ；否则，返回 false
     */
    class MyQueue {
        public Stack<Integer> test1;
        public Stack<Integer> test2;
        public MyQueue() {
            this.test1 = new Stack<>();//用于存储
            this.test2 = new Stack<>();//用于把第一个压入栈的元素 外存起来
        }

        public void push(int x) {
            this.test1.push(x);
        }

        public int pop() {
            if (!this.test1.isEmpty()) {
                while (true) {//找到test1的压入的第一个元素
                    int cmp = this.test1.pop();
                    if (this.test1.isEmpty()) {
                        while (!this.test2.isEmpty()) {//把test2暂存的元素 重新转到test1
                            int cmp2 = this.test2.pop();
                            this.test1.push(cmp2);
                        }
                        return cmp;
                    }
                    this.test2.push(cmp);
                }
            }
            return -1;

        }

        public int peek() {
            while (true) {//找到test1的压入的第一个元素
                int cmp = this.test1.pop();
                if (this.test1.isEmpty()) {
                    this.test2.push(cmp);//新增了 把最后一个元素暂存到test2
                    while (!this.test2.isEmpty()) {//把test2暂存的元素 重新转到test1
                        int cmp2 = this.test2.pop();
                        this.test1.push(cmp2);
                    }
                    return cmp;
                }
                this.test2.push(cmp);
            }
        }

        public boolean empty() {
            return this.test1.isEmpty() && this.test2.isEmpty();
        }
    }


    /**
     * Your MyQueue object will be instantiated and called as such:
     * MyQueue obj = new MyQueue();
     * obj.push(x);
     * int param_2 = obj.pop();
     * int param_3 = obj.peek();
     * boolean param_4 = obj.empty();
     */
    /*
    请你仅使用两个队列实现一个后入先出（LIFO）的栈，
    并支持普通栈的全部四种操作（push、top、pop 和 empty）。

    实现 MyStack 类：

    void push(int x) 将元素 x 压入栈顶。
    int pop() 移除并返回栈顶元素。
    int top() 返回栈顶元素。
    boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
     */
    class MyStack {
        private Queue<Integer> text1;
        private Queue<Integer> text2;
        public MyStack() {
            text1 = new LinkedList<>();
            text2 = new LinkedList<>();
        }

        public void push(int x) {
            if (text1.isEmpty() && text2.isEmpty()) {
                text1.offer(x);
                return;
            }
            if (text1.isEmpty()) {//往不为空的队列存
                text2.offer(x);
            }else {
                text1.offer(x);
            }

        }

        public int pop() {
            if (text1.isEmpty()) {
                while (true) {
                    int cmp = text2.poll();//先弹出来
                    if (!text2.isEmpty()) {//不为空时,说明这个不是最后一个
                        text1.offer(cmp);//存入另一个队列
                    }else {
                        return cmp;
                    }
                }
            }else {
                while (true) {
                    int cmp = text1.poll();
                    if (!text1.isEmpty()) {
                        text2.offer(cmp);
                    }else {
                        return cmp;
                    }
                }
            }
        }

        public int top() {
            if (text1.isEmpty()) {
                while (true) {
                    int cmp = text2.poll();//先弹出来
                    if (!text2.isEmpty()) {//不为空时,说明这个不是最后一个
                        text1.offer(cmp);//存入另一个队列
                    }else {
                        text1.offer(cmp);//加了一条  把最后一个元素 在存入队列
                        return cmp;
                    }
                }
            }else {
                while (true) {
                    int cmp = text1.poll();
                    if (!text1.isEmpty()) {
                        text2.offer(cmp);
                    }else {
                        text1.offer(cmp);
                        return cmp;
                    }
                }
            }
        }

        public boolean empty() {
            if (text1.isEmpty() && text2.isEmpty()) {
                return true;
            }
            return false;
        }
    }

    /**
     * Your MyStack object will be instantiated and called as such:
     * MyStack obj = new MyStack();
     * obj.push(x);
     * int param_2 = obj.pop();
     * int param_3 = obj.top();
     * boolean param_4 = obj.empty();
     */
    /*
    设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

    实现 MinStack 类:

    MinStack() 初始化堆栈对象。
    void push(int val) 将元素val推入堆栈。
    void pop() 删除堆栈顶部的元素。
    int top() 获取堆栈顶部的元素。
    int getMin() 获取堆栈中的最小元素
     */
    class MinStack {
        private Stack<Integer> test1;
        private Stack<Integer> test2;
        public MinStack() {
            this.test1 = new Stack<>();;
            this.test2 = new Stack<>();;
        }

        public void push(int val) {
            this.test1.push(val);
            if (this.test2.empty()) {
                this.test2.push(val);
            }else if (this.test2.peek() >= val) {
                this.test2.push(val);
            }
        }

        public void pop() {
            int cmp = this.test1.pop();
            if (cmp == test2.peek()) {
                test2.pop();
            }
        }

        public int top() {
            return test1.peek();
        }

        public int getMin() {
            return test2.peek();
        }
    }

    /**
     * Your MinStack object will be instantiated and called as such:
     * MinStack obj = new MinStack();
     * obj.push(val);
     * obj.pop();
     * int param_3 = obj.top();
     * int param_4 = obj.getMin();
     */
    /*
    给你一个链表的头节点 head 和一个整数 val ，
    请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点
     */
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        ListNode nullHead = new ListNode(-1);
        nullHead.next = head;
        ListNode run = nullHead;
        ListNode runNext = run.next;
        while (runNext != null) {
            if (runNext.val == val) {
                run.next = runNext.next;
            }else {
                run = run.next;
                runNext = runNext.next;
            }
        }
        return head;
    }
    /*
    给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null
     */
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        ListNode A1 = head;//每次一步
        ListNode A2 = head;//每次两步 从第二个开始走,防止一开始就相等 然后返回true
        while (A1 != null && A2 != null) {//如果是环 那么总有一次会相等
            A1 = A1.next;
            A2 = A2.next;
            if (A2 != null) {
                A2 = A2.next;
            }
            if (A1 == A2) {
                ListNode run1 = head;
                ListNode run2 = A1;
                while (run1 != run2) {
                    run1 = run1.next;
                    run2 = run2.next;
                }
                return run1;
            }

        }
        return null;
    }
    /*
    如果链表中存在环 ，则返回 true 。 否则，返回 false
     */
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        ListNode A1 = head;//每次一步
        ListNode A2 = head.next;//每次两步 从第二个开始走,防止一开始就相等 然后返回true
        while (A1 != null && A2 != null) {//如果是环 那么总有一次会相等 不是环总有一次会跑到null 然后返回false
            if (A1 == A2) {
                return true;
            }else {
                A1 = A1.next;
                A2 = A2.next;
                if (A2 != null) {
                    A2 = A2.next;
                }
            }
        }
        return false;
    }
    /*
    给你两个单链表的头节点 headA 和 headB ，
    请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null
     */
     public class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
             val = x;
             next = null;
        }
    }
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = 0;//记录两个链表的长度
        int lenB = 0;

        ListNode runA = headA;
        ListNode runB = headB;
        while (runA != null) {
            lenA++;
            runA = runA.next;
        }
        while (runB != null) {
            lenB++;
            runB = runB.next;
        }

        int sub = lenA - lenB;
        runA = headA;
        runB = headB;
        if (sub > 0) {
            while (sub != 0) {
                runA = runA.next;
                sub--;
            }
        }else {
            while (sub != 0) {
                runB = runB.next;
                sub++;
            }
        }
        while (runA != null && runB != null) {
            if (runA == runB) {
                return runA;
            }else {
                runA = runA.next;
                runB = runB.next;
            }
        }
        return null;

    }

    /*
    给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。
    你不能使用任何內建的用于处理大整数的库（比如 BigInteger），
    也不能直接将输入的字符串转换为整数形式。(不能用库函数的意思)
     */
    public static void main3(String[] args) {
        //如果数字更加庞大,此时我们要模拟出进位
        Scanner scanner = new Scanner(System.in);
        String num1 = scanner.nextLine();
        String num2 = scanner.nextLine();

        int i = num1.length() - 1, j = num2.length() - 1, add = 0;//add是进位的数
        StringBuffer ans = new StringBuffer();
        while (i >= 0 || j >= 0 || add != 0) {
            int x = i >= 0 ? num1.charAt(i) - '0' : 0;
            int y = j >= 0 ? num2.charAt(j) - '0' : 0;
            int result = x + y + add;
            ans.append(result % 10);//如果x+y+add进位了(大于9),那么只取个位数
            add = result / 10;//取十位的进位数
            i--;
            j--;
        }
        // 计算完以后的答案需要翻转过来
        ans.reverse();
        System.out.println(ans.toString());
    }
    public static void main2(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String num1 = scanner.nextLine();
        String num2 = scanner.nextLine();

        long num11 = 0;
        for (int i = 0; i < num1.length(); i++) {
            num11 = num11 * 10 + num1.charAt(i) - '0';
        }
        long num22 = 0;
        for (int i = 0; i < num2.length(); i++) {
            num22 = num22 * 10 + num2.charAt(i) - '0';
        }
        long sum = num11 + num22;
        String ret = String.valueOf(sum);
        System.out.println(ret);
    }
    public static void main1(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String input = scanner.nextLine();

        int[] arr = new int[26];//存放26个英文单词,顺序从a到z
        for (int i = 0 ; i < input.length() ; i++) {
            int num = input.charAt(i);//读取当前位置的字符,并把相对应的ASCII码存入num中
            arr[num-97]++;//相应位置的数组加一
        }
        for (int i = 0 ; i < input.length() ; i++) {
            int num = input.charAt(i);
            if (arr[num-97] == 1) {
                System.out.println(i);
                return;
            }
        }
        System.out.println("-1");
        return;
    }
}